/*
 *  kdMemAlloc.h
 *  kangmodb
 *
 *  Created by 강모 김 on 11. 5. 9..
 *  Copyright 2011 강모소프트. All rights reserved.
 *
 */

#include "kdInfra.h"
#include "types.h"
#include "util.h"

/** @brief The memory header that comes right before the address returned by alloc function.
 * Both the header and footer are 32 bits wide. 
 *
 * This helps to align the returned address aligned to 8 bytes boundary for fixed size allocators.
 * ( Assuming that the size of allocated area is also aligned to 8 bytes )
 *
 * U : Unused space
 * H : Header
 * F : Footer
 * 
 * 0   4   8   12  16  20  24  28  32  36  42 ...
 * +-------------------------------------------------------...
 * | U | H | allocated area        | F | H |  alloced area ...
 * +-------------------------------------------------------...
 */
typedef struct kdMemHeader
{
	/** @brief The number of zero bits on the right side of the mask for getting the allocator object from an allocated memory.
	 * This is for calculating the address of the allocator object from the address of allocated slot.
	 * The beginning address of the memory chunk is aligned to power of two. 
	 * Because we put the allocator object at the beginning of the chunk so (AllocatedMemory & allocatorMask) equals to the address of allocator object.
	 * For example, assume a chunk with size 1MB. The start address of the chunk is also aligned to 1MB boundary,
	 * and allocatorMask equals to (0b 1111 1111 1111 0000 0000 0000 0000 0000).
	 * 
	 * In this case, it zeroBitsForAllocatorMask equals to 20.
	 */
	u32 zeroBitsForAllocatorMask:6; // Why 6 bits? 6 bits can have values from 0 to 63. No need to store value "64", because we won't have such a big memory chunk that uses entire memory space of 64 bits.

	/** @brief The allocated size. The allocated memory size is always multiples of 8 bytes. 
	 * So we store the count of 8 byte unit instead of the actual size.
	 * The largest size of memory that this allocator can allocate is 128K bytes, which is 16K of 8 byte units. To keep 16K, we need 14 bits.
	 */
	u32 sizeWithCountOf8Bytes:14;

	/** @brief Can be used for a magic value for checking if the memory area was overwritten.
	 */
	u32 magic:12;
}kdMemHeader;

/** @brief The footer at the end of each allocated memory slot is same to the footer.
 */
typedef kdMemHeader kdMemFooter;

/** @brief The 12 bit magic stored in kdMemHeader 
 */
const u32 KD_MEM_HEADER_MAGIC=(u32)0x00000FED;

/** @brief The maximum size of memory that we can allocate is 128K. Why? see the comment on kdMemHeader.sizeWithCountOf8Bytes.
 */
const u32 KD_MEM_MAX_ALLOC_SIZE=131072;

/** @brief See if the memory header has the valid magic value 
 */
inline bool kdMemHasValidMagic(kdMemHeader * header)
{
	return header->magic == KD_MEM_HEADER_MAGIC;
}

/** @brief Set the magic value to the header.
 */
inline void kdMemSetMagic(kdMemHeader * header)
{
	header->magic = KD_MEM_HEADER_MAGIC;
}

/** @brief Get the size of allocated memory from the header.
 */
inline u32 kdMemGetAllocatedSize( kdMemHeader * header )
{
	KD_DASSERT( header != NULL );
	return ( ((u32)header->sizeWithCountOf8Bytes) << 3 );
}

/** @brief Get the size of allocated memory from the header.
 */
inline void kdMemSetAllocatedSize( kdMemHeader * header, u32 allocatedSize )
{
	KD_DASSERT( header != NULL );
	// Make sure that the allocatedSize is aligned to 8 bytes. The lowest 3 bits should be 0.
	// First, shift the size to right by 3 bits, to left by 3 bits to clear the lowest 3 bits to 0.
	// And then, see if it is equal to the original allocatedSize.
	KD_DASSERT( ((allocatedSize >> 3) << 3) == allocatedSize);
	
	header->sizeWithCountOf8Bytes = (allocatedSize >> 3);
}

/** @brief The type of magic value for checking somebody overwritten the memory chunk. 
 */
typedef u64 kdChunkMagic;

/** @brief The magic value to set to kdMemAlloc.magic 
 */
const u64 KD_MEMORY_ALLOCATOR_MAGIC_VALUE = 0xcafebece06220403;

/** @brief Set the magic value for the chunk at the beginning and end of the chunk.
 */
inline void kdMemSetChunkMagic( void * chunkAddr, uptr chunkSize )
{
	kdChunkMagic * magicAtBegin = (kdChunkMagic *) chunkAddr;
	kdChunkMagic * magicAtEnd = (kdChunkMagic *) ((char*) chunkAddr + chunkSize - sizeof(kdChunkMagic));
	*magicAtBegin = KD_MEMORY_ALLOCATOR_MAGIC_VALUE;
	*magicAtEnd = KD_MEMORY_ALLOCATOR_MAGIC_VALUE;
}

/** @brief Check if the memory chunk has a valid magic values 
 */
inline bool kdMemChunkHasValidMagic( void * chunkAddr, uptr chunkSize )
{
	kdChunkMagic * magicAtBegin = (kdChunkMagic *) chunkAddr;
	kdChunkMagic * magicAtEnd = (kdChunkMagic *) ((char*) chunkAddr + chunkSize - sizeof(kdChunkMagic));
	bool magicAtBeginOK = (*magicAtBegin == KD_MEMORY_ALLOCATOR_MAGIC_VALUE);
	bool magicAtEndOK = (*magicAtEnd == KD_MEMORY_ALLOCATOR_MAGIC_VALUE);
	return magicAtBeginOK + magicAtEndOK;
}

/** @brief Set zeroBitsForAllocatorMask based on the size of chunk 
 */
inline void kdMemSetChunkSize( kdMemHeader * header, uptr chunkSize)
{
	KD_ASSERT( chunkSize > 0 );
	KD_DASSERT( header != NULL );

	u32 zeroBits = 0;
	for(;(chunkSize & 0x1) == 0; chunkSize = chunkSize >> 1)
	{
		zeroBits ++;
	}
	
	// chunkSize should be power of 2. It means there should be only one bit whose value is 1.
	KD_ASSERT( chunkSize == 0x1 );

	// zeroBits should not be 0.
	KD_ASSERT( zeroBits > 0 );
	header->zeroBitsForAllocatorMask = zeroBits;
}

/** @brief Get the size of memory chunk 
 */
inline uptr kdMemGetChunkSize( kdMemHeader * header )
{
	KD_DASSERT( header != NULL );
	return (uptr)1 << header->zeroBitsForAllocatorMask;
}

/** @brief Get the address of memory chunk from the header of a memory slot. 
 */
inline void * kdMemGetChunkAddr( kdMemHeader * header )
{
	KD_DASSERT( header != NULL);
	
	// Shift the address to right by N bits, and then shift it to left by N bits to set the low N bits to 0.
	// Here, N is header->zeroBitsForAllocatorMask.
	void* chunkAddr = (void*) (((uptr)header >> (u32)header->zeroBitsForAllocatorMask ) << (u32)header->zeroBitsForAllocatorMask) ;
	
	KD_DASSERT( kdMemChunkHasValidMagic(chunkAddr, kdMemGetChunkSize(header) ) );
	
	return chunkAddr;
}

/** @brief Get the address of memory allocator from the header of a memory slot. 
 */
inline void * kdMemGetAllocator( void * chunkAddr )
{
	return ((char*)chunkAddr) + sizeof(kdChunkMagic);
}
inline void * kdMemGetAllocator( kdMemHeader * header )
{
	return kdMemGetAllocator( kdMemGetChunkAddr(header) );
}


/** @brief The header stored in each free memory slot. It comes right after the kdMemHeader struct.
 *
 * A free memory slot : 
 *                       |<-------- The part used to store data -------->|
 * +-------------------------------------------------------------------------------------------+
 * | kdMemHeader(32bits) | hdFreeMemHeader(32/64bits) |   Unused Space   | kdMemFooter(32bits) |
 * +-------------------------------------------------------------------------------------------+
 */
typedef struct kdFreeMemHeader
{
	/** @brief The next free memory slot
	 */
	struct kdFreeMemHeader * next;
} kdFreeMemHeader;

/** @brief The interface for memory allocator. 
 */
class kdMemAlloc
{
public :
	/** @brief Initialize the memory allocator.
	 * @param memChunk The memory chunk where this allocator allocates small slots of memory.
	 * @param memChunkSize The total size of memory allocated to memChunk.
	 * @param allocDesc The descriptor of a specific allocator. Differs from allocators to allocators.
	 */
	virtual KD_VOID initialize(void * memChunk, uptr memChunkSize, void * allocDesc ) = 0;

	/** @brief Allocate a specific size of memory slot.
	 * @param memSize The size of memory to allocate.
	 * @param mem The allocated memory is set to *mem.
	 */
	virtual KD_VOID alloc(uptr memSize, void ** mem) = 0;

	/** @brief Free an allocated memory slot.
	 */
	virtual KD_VOID free(void *mem) =0;
	
	/** @brief Destroys the memory allocator object.
  	 */
	virtual KD_VOID destroy() = 0;

	/** @brief Verify if the allocated memory slot is valid 
	 */
	KD_INLINE bool kdMemVerify( void * mem )
	{
		kdMemHeader* header = (((kdMemHeader*)mem) -1 );
		void * chunkAddr = kdMemGetChunkAddr(header);
		uptr   chunkSize = kdMemGetChunkSize(header);
		
		KD_ASSERT( kdMemHasValidMagic(header) );
		KD_ASSERT( kdMemChunkHasValidMagic(chunkAddr, chunkSize) );
		return true;
	}
	
	/** @brief Calculate the address of allocator object, call free function on it.
	 * By using this function, garbage collectors can free memory without knowing the allocator object.
  	 */
	static KD_VOID freeWithAllocator(void *mem)
	{
		KD_TRY
		{	
			// TODO : Verification consider checking this on Release build.
			KD_DASSERT( kdMemVerify(mem) );
			
			// The header comes right before the allocated address.
			kdMemHeader* header = (((kdMemHeader*)mem) -1 );
			void * chunkAddr = kdMemGetChunkAddr(header);
			kdMemAlloc* allocator = (kdMemAlloc*)kdMemGetAllocator(chunkAddr);
			KD_CALL( allocator->free( mem ) );
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}
};

/** @brief The descriptor for the fixed memory allocator.
 * A temporary structure for passing initialization information to the initialize function of the memory allocator.
 */
typedef struct kdFixedMemAllocDesc
{
	/** @brief The fixed size of allocated memory. The memSize parameter of alloc function should be this size always.
	 */
	uptr fixedMemSize;
	/** @brief The beginning address of slot area. Inclusive.
	 */
	void* slotAreaBeginIncl;
	/** @brief The end address of slot area. Exclusive.
	 */
	void* slotAreaEndExcl;
}kdFixedMemAllocDesc;

/** @brief The fixed memory allocator. Always allocates a fixed size of memory slots.
 *  The object comes rigth after the magic value in the chunk where memory slots are allocated.
 *
 * |<---------------------- Chunk -------------------------------------------------->|
 * +---------------------------------------------------------------------------------+
 * |kdChunkMagic| kdFixedMemAlloc | MemSlot | MemSlot | ..... | MemSlot |kdChunkMagic|
 * +---------------------------------------------------------------------------------+
 */
class kdFixedMemAlloc : public kdMemAlloc
{
private :
	/** @brief The fixed size of allocated memory. The memSize parameter of alloc function should be this size always.
	 */
	uptr fixedMemSize_;
	
	/** @brief The size of chunk that this allocator can use. 
	 */
	uptr memChunkSize_;
	
	/** @brief The linked list that keeps all free memory slots.
	 */
	kdFreeMemHeader * freeMemList_;

	/** @brief Initialize a memory slot. See the comment on kdFreeMemHeader struct for the details.
	 */
	KD_VOID initMemSlot(kdMemHeader * slot)
	{
		KD_TRY
		{
			kdMemHeader * header = (kdMemHeader*) slot;
			kdMemSetMagic( header );
			kdMemSetAllocatedSize( header, fixedMemSize_ );
			kdMemSetChunkSize( header, memChunkSize_ );
		
			// Set header to footer.
			kdMemFooter * footer = (kdMemFooter*) ((char*)(header + 1) + fixedMemSize_);
			*footer = *((kdMemFooter*)header);

			KD_ASSERT( kdMemIsAlignedBy8Byte( (uptr) (slot + 1) ) );
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}

	/** @brief Slice the chunk by fixed size, add each memory slot to the free list.
	 * @param slotAreaBeginIncl The beginning address of slot area. Inclusive.
	 * @param slotAreaEndExcl The end address of slot area. Exclusive.
	 */
	KD_VOID sliceChunkByFixedSize(void * slotAreaBeginIncl, void * slotAreaEndExcl)
	{
		KD_TRY
		{
			uptr sizePerSlot = sizeof(kdMemHeader) + fixedMemSize_ + sizeof(kdMemFooter);
			
			// The free slots come right after the allocator object within a chunk. See the comment on the class kdFixedMemAlloc.
			// To align the address returned by alloc interface by 8 bytes, need to skip the footer size(4 bytes).
			// See the comment on kdMemHeader for the details.
			for (char * ptr = (char*)kdMemAlignUp(slotAreaBeginIncl,8)+sizeof(kdMemFooter); 
			     (ptr+sizePerSlot) < slotAreaEndExcl; 
				 ptr += sizePerSlot )
			{
				kdMemHeader * slot = (kdMemHeader*) ptr;
				KD_CALL( initMemSlot( slot ) );
				KD_CALL( addToFreeList( (kdFreeMemHeader*)(slot + 1 ) ) );
			}
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}
	
	/** @breif Add a free slot into the free list 
	 */
	KD_VOID addToFreeList( kdFreeMemHeader * freeHeader)
	{
		KD_TRY
		{
			KD_ASSERT( freeHeader != NULL );
			
			freeHeader->next = freeMemList_;
			freeMemList_ = freeHeader;
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}

	/** @brief Remove a free slot from the free list. Set it to *freeHeader. If no free slot is available, set *freeHeader to NULL. */
	KD_VOID removeFromFreeList( kdFreeMemHeader ** freeHeader )
	{
		KD_TRY
		{
			KD_ASSERT( freeHeader != NULL );
			
			kdFreeMemHeader * removedFreeSlot = freeMemList_;
			if ( freeMemList_ != NULL )
			{
				freeMemList_ = freeMemList_->next;
			}
			*freeHeader = removedFreeSlot;
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}

public :
	kdFixedMemAlloc()
	{
	}

	virtual ~kdFixedMemAlloc()
	{
	}
	
	/** @brief Initialize the memory allocator.
	 * For the description on parameters, see kdMemAlloc::initialize.
	 * Throw KD_EXCP_MEM_CHUNK_SIZE_NOT_POWER_OF_TWO if memChunkSize is not power of two.
	 * Throw KD_EXCP_MEM_CHUNK_NOT_ALIGNED if memChunk pointer is not aligned by memChunkSize.
	 */
	virtual KD_VOID initialize(void * memChunk, uptr memChunkSize, void * allocDesc )
	{
		KD_TRY
		{
			// Verify that "this" object exists within the chunk.
			KD_ASSERT(this == kdMemGetAllocator(memChunk));
			KD_ASSERT(allocDesc != NULL);
			
			// Make sure the memory chunk size is power of two.
			if ( ! kdMemIsPowerOfTwo(memChunkSize) ) 
			{
				KD_THROW( KD_EXCP_MEM_CHUNK_SIZE_NOT_POWER_OF_TWO );
			}
			
			// Make sure the memChunk pointer is aligned by memChunkSize.
			// This is necessary to get the beginning address of a memchunk from any memory address allocated within the chunk.
			if ( kdMemGetAlignedBits((uptr)memChunk) != kdMemGetAlignedBits(memChunkSize) )
			{
				KD_THROW( KD_EXCP_MEM_CHUNK_NOT_ALIGNED );
			}
			
			memChunkSize_ = memChunkSize;
			
			fixedMemSize_      = ((kdFixedMemAllocDesc*)allocDesc)->fixedMemSize;
			
			freeMemList_ = NULL;

			KD_CALL( sliceChunkByFixedSize(((kdFixedMemAllocDesc*)allocDesc)->slotAreaBeginIncl, ((kdFixedMemAllocDesc*)allocDesc)->slotAreaEndExcl) );
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}

	/** @brief Allocate a specific size of memory slot.
	* Throws KD_EXCP_NO_MEM if no more memory slots exist.
	*/
	virtual KD_VOID alloc(uptr memSize, void ** mem) 
	{
		KD_TRY
		{
			KD_ASSERT( memSize == fixedMemSize_ );
			KD_DASSERT( mem != NULL );
		
			kdFreeMemHeader * slot;
			
			KD_CALL( removeFromFreeList( & slot ) );

			// No more slots
			if (slot == NULL )
			{
				KD_THROW(KD_EXCP_CHUNK_MEM_OUT_OF_FREESLOTS);
			}
			
			KD_DASSERT( kdMemVerify( slot ) );
			
			*mem = slot;
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}

	/** @brief Free an allocated memory slot.
	 */
	virtual KD_VOID free(void *mem)
	{
		KD_TRY
		{
			kdFreeMemHeader * slot = (kdFreeMemHeader*) mem;
			
			KD_DASSERT( kdMemVerify( slot ) );
			
			KD_CALL( addToFreeList( slot ) );
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}

	/** @brief Destroys the memory allocator object.
  	 */
	virtual KD_VOID destroy()
	{
		KD_TRY
		{
			// Nothing to do.
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}
	
	/** @brief The initializer of fixed memory allocator. Rather than directly initializing with initialize(...) function, use this function.
	 */
	static KD_VOID create( void * memChunk, uptr memChunkSize, uptr fixedMemSize, kdFixedMemAlloc ** allocator)
	{
		KD_TRY
		{
			kdFixedMemAllocDesc allocDesc;
			allocDesc.fixedMemSize = fixedMemSize;
			
			// The allocator object comes right after the magic within the chunk.
			void * allocatorAddr = kdMemGetAllocator(memChunk);

			// The slot address begins right after the allocator object.
			allocDesc.slotAreaBeginIncl = (char*)allocatorAddr + sizeof(kdFixedMemAlloc);
			// We can use memory to the end of chunk, however we need to reserve the area for the chunk magic at the end of chunk.
			allocDesc.slotAreaEndExcl = (char*)memChunk + memChunkSize - sizeof(kdChunkMagic);
			
			// Set magic values on the memory chunk.
			kdMemSetChunkMagic( memChunk, memChunkSize );
			
			// To locate the memory allocator at offset 0 of the memory chunk, pass the address of the memChunk to "new" operator.
			kdFixedMemAlloc * alloc = new(allocatorAddr) kdFixedMemAlloc();
			
			KD_CALL( alloc->initialize( memChunk, memChunkSize, &allocDesc) );
			
			*allocator = alloc;
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}
	
	/** @brief Destroys the allocator object. You should not call delete operator directly on an object created by above create function, but use this destroy function.
	 */
	static KD_VOID destroy(kdFixedMemAlloc * allocator)
	{
		KD_ASSERT( allocator != NULL );
		KD_TRY
		{
			KD_CALL( allocator->destroy() );
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}
};